namespace LeetCode0218SkylineProblem {

    /**
     * Constraints:
     *  1 <= buildings.length <= 104
     *  0 <= lefti < righti <= 231 - 1
     *  1 <= heighti <= 231 - 1
     *  buildings is sorted by lefti in non-decreasing order.
     * 
     * 如题可知：
     * 地平线上的连续灰度矩形叠加问题，通过记录数据压缩
     * （将建筑看做标准矩形，建筑轮廓可以描绘成标准矩形线框；仅存储每个灰度矩形的左上角坐标，可以有效减少数据量）
     * 最简便写法：使用map做扫描统计，但是考虑到数据量巨大，以及可能出现非整型数据，使用map统计非常不方便，不可取。
     * 此时，我需要一个数据结构记录矩形的左右边界以及高度，即使用一个数组记录顶部线段即可(这一步可以看做图形灰度化，图形顶端线段化)，按照x升序排序，方便输出绘制图形。
     * 此后，进一步压缩存储数据，记录线段的左上角顶点，最终以右下角（x，0）收尾，可以完整的存储上一步得到的线段数据，再次无损压缩存储数据。
     * （题外话：这道题，在网络传输图形数据时非常实用，所以我特别感兴趣！！！）
     * @param buildings 
     */
    function getSkyline(buildings: number[][]): number[][] {
        // 出来异常输入，即无建筑模型数据
        if (!buildings || buildings.length == 0)
            return [];
        // 数据转换录入：将单独的建筑矩形，录入成为灰度建筑矩形（即剔除重叠部分，重新划分矩形）
        let data: DataLine[] = new Array(); // 这是一个x轴方向上连续的线段数组，且保证是升序衔接排列的
        buildings.forEach((v: number[]) => {
            // 防止输入不合法程序意外崩溃
            if (!v || v.length < 3) return;
            // 此处不作额外的数据检测，题设输入都是符合要求的
            const left = v[0];
            const right = v[1];
            const height = v[2];
            // 两矩形之间的关系判断，包含、相交、相离，转换成线段关系
            // ps: 题设 buildings 按 lefti 非递减排序,所以不需要判断已序数组的左侧边界
            if (!data || data.length == 0) {
                // 无数据，直接填入
                data.push({ left, right, height });
            } else {
                const size: number = data.length;
                // 已记录线段最大右侧边界
                const oldMaxRight = data[size - 1].right;
                if (left >= oldMaxRight) {
                    // 这里将相离和相邻一起处理了
                    if (left > oldMaxRight) {
                        // 先补充空缺的一段0高度地平线
                        data.push({ left: oldMaxRight, right: left, height: 0 });
                    }
                    // 填充新数据(需要先判别是否与前一个相邻线段等高，等高则合并)
                    if (data[size - 1].height == height)
                        data[size - 1].right = right;
                    else
                        data.push({ left, right, height });
                }
                else {
                    // 相交关系可以拆分成：包含+相邻
                    // 先存入相邻部分
                    data.push({ left: oldMaxRight, right, height });
                    // 然后更新包含区域的内容(数组倒叙遍历,分段处理)
                    let tpIdx = size - 1; // 索引使用旧size即可，重新计算数组长度没必要（新增的内容不需要判断）
                    // 两线段有重叠，需要重新采样计算高度
                    while (left < data[tpIdx].right) {
                        // 原始灰度图高度较高，无需处理该片段
                        if (data[tpIdx].height >= height) {
                            tpIdx--;
                            continue;
                        }
                        // 需要更新高度的情况如下:
                        if (left <= data[tpIdx].left) {
                            // 选段全覆盖，直接更新高度即可
                            data[tpIdx].height = height;
                            // TODO 因为修改了高度，故需要判别是否与后一个相邻线段等高，等高则合并
                            tpIdx--;
                        } else {
                            // 选段仅被覆盖部分，需要拆分线段，插入新数组，并结束循环
                            data[tpIdx].right = left;   // 更新原始线段右侧边界
                            // 在该数据右侧插入新数据
                            // data.splice(tpIdx + 1, 0, {});
                            break;
                        }
                    }
                }
            }
            // TODO HarryNR 今天没空，暂时这样
        });
    };

    /**
     * 建筑矩形对象数据结构
     * 用顶部线段表示灰度矩形的简略数据
     * 注意事项：
     * 用该类型组成一个数组存储连续建筑，需要保证无重复，无断点
     */
    interface DataLine {
        left: number,    // 矩形左侧坐标
        right: number,   // 矩形右侧坐标
        height: number   // 矩形高度
    }

}